package wheel.dataStruct.impl;

import java.util.Arrays;

/**
 * 二叉堆
 */
public class BinaryHeap<E extends Comparable> {

    private Object[] arr;
    private int size = 0;

    public BinaryHeap() {
        this(11);
    }

    public BinaryHeap(int capacity){
        this.arr = new Object[capacity];
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public int size(){
        return size;
    }

    /**
     * 插入元素
     * @param element
     */
    public void insert(E element){
        if(element==null)
            throw new NullPointerException();
        int index = size;
        if(index >= arr.length)
            grow(index + 1);
        size++;
        if (index == 0) {
            arr[0] = element;
        }else {
            siftUp(index, element);
        }
    }

    /**
     * 二叉堆上浮操作
     * @param index
     * @param element
     */
    private void siftUp(int index, E element) {
        Comparable<? super E> elementComparable = (Comparable<? super E>) element;
        while(index > 0){
            int parentIndex = (index - 1) >>> 1;
            Object parentElement = arr[parentIndex];
            /**
             * 这里没有区分二叉堆的最大堆和最小堆，Comparable的比较值大就上浮
             */
            if(elementComparable.compareTo((E)parentElement) <= 0)
                break;
            arr[index] = parentElement;
            index = parentIndex;
        }
        arr[index] = element;
    }

    /**
     * 扩张数组
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        //TODO
    }

    /**
     * 仅消费
     * @return
     */
    public E peek(){
        if(size == 0)
            return null;
        return (E)arr[0];
    }

    /**
     * 弹出
     * @return
     */
    public E poll(){
        if(size == 0)
            return null;
        size--;
        Object resultElement = arr[0];
        Object endElement = arr[size];
        arr[size] = null;
        if(size != 0)
            siftDown(0, endElement);
        return (E)resultElement;
    }

    /**
     * 下沉操作
     * @param downIndex
     * @param endElement
     */
    private void siftDown(int downIndex, Object endElement) {
        Comparable<? super E> endElementComparable = (Comparable<? super E>) endElement;
        int half = size >>> 1;
        while(downIndex < half){
            int leftIndex = (downIndex << 1) + 1;
            Object downElement = arr[leftIndex];
            int rigthIndex = leftIndex + 1;
            if(rigthIndex < size && ((Comparable<? super E>)arr[rigthIndex]).compareTo((E)downElement)>0)
                downElement = arr[leftIndex = rigthIndex];
            if(endElementComparable.compareTo((E)downElement)>0)
                break;
            arr[downIndex] = downElement;
            downIndex = leftIndex;
        }
        arr[downIndex] = endElement;
    }


    @Override
    public String toString() {
        return "BinaryHeap{" +
                "arr=" + Arrays.toString(arr) +
                ", size=" + size +
                '}';
    }

    public void showStruct(){

    }
}
